<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>

</body>
<script>
    /**
     * 二叉搜索树节点类
     * @class
     */
    class Node{
        /**
         * 创建新节点
         * @constructor
         * @param {number} value - 节点存储的数值
         */
        constructor(value){
            this.value = value
            this.left = null
            this.right = null
        }
    }

    /**
     * 二叉搜索树实现类
     * @class
     */
    class BinaryTree{
        /**
         * 初始化空树
         * @constructor
         */
        constructor(){
            this.root = null
        }

        /**
         * 向树中插入新节点
         * @param {number} value - 要插入的数值
         */
        insert(value){
            const newNode = new Node(value)
            if(this.root === null){
                this.root = newNode
                return
            }
            this._insertNode(this.root,newNode)
        }

        /**
         * 递归插入节点辅助方法
         * @private
         * @param {Node} node - 当前遍历到的节点
         * @param {Node} newNode - 待插入的新节点
         */
        _insertNode(node,newNode){
            // 新节点值大于当前节点则向右子树插入
            if(node.value < newNode.value){
                if(node.right === null){
                    node.right = newNode
                } else {
                    this._insertNode(node.right,newNode)
                }
            }
            // 新节点值小于当前节点则向左子树插入
            else {
                if(node.left === null){
                    node.left = newNode
                } else {
                    this._insertNode(node.left,newNode)
                }
            }
        }

        /**
         * 检查树中是否存在指定值
         * @param {number} value - 要查找的数值
         * @returns {boolean} 是否存在该值
         */
        search(value){
            return this._searchNode(this.root,value)
        }

        /**
         * 递归搜索节点辅助方法
         * @private
         * @param {Node} node - 当前遍历到的节点
         * @param {number} value - 要查找的数值
         * @returns {boolean} 当前子树是否存在该值
         */
        _searchNode(node,value){
            if(node === null) return false
            if(node.value === value) return true
            // 根据值大小决定搜索方向
            if(node.value < value){
                return this._searchNode(node.right,value)
            } else {
                return this._searchNode(node.left,value)
            }
        }

        /**
         * 执行前序遍历（根节点 -> 左子树 -> 右子树）
         */
        preOrder(){
            this._preOrderTraversal(this.root);
        }

        /**
         * 递归前序遍历辅助方法
         * @private
         * @param {Node} node - 当前遍历到的节点
         */
        _preOrderTraversal(node){
            if(node){
                console.log(node.value)
                this._preOrderTraversal(node.left)
                this._preOrderTraversal(node.right)
            }
        }

        /**
         * 执行中序遍历（左子树 -> 根节点 -> 右子树）
         */
        inOrder(){
            this._inOrderTraversal(this.root)
        }

        /**
         * 递归中序遍历辅助方法
         * @private
         * @param {Node} node - 当前遍历到的节点
         */
        _inOrderTraversal(node){
            if(node){
                this._inOrderTraversal(node.left)
                console.log(node.value)
                this._inOrderTraversal(node.right)
            }
        }

        /**
         * 执行后序遍历（左子树 -> 右子树 -> 根节点）
         */
        postOrder(){
            this._postOrderTraversal(this.root)
        }

        /**
         * 递归后序遍历辅助方法
         * @private
         * @param {Node} node - 当前遍历到的节点
         */
        _postOrderTraversal(node){
            if(node){
                this._postOrderTraversal(node.left)
                this._postOrderTraversal(node.right)
                console.log(node.value)
            }
        }

        /**
         * 执行层序遍历（广度优先遍历）
         * 使用队列按层级遍历所有节点
         */
        levelOrder(){
            // 空树直接返回
            if(this.root === null) return
            const queue = [this.root]

            while(queue.length > 0){
                const current = queue.shift()
                console.log(current.value)
                // 将子节点加入队列尾部
                if(current.left) queue.push(current.left)
                if(current.right) queue.push(current.right)
            }
        }

        /**
         * 查找树中的最小值
         * @returns {number} 树中的最小数值
         */
        findMin(){
            let current = this.root
            // 持续向左子树遍历直到叶子节点
            while(current.left){
                current = current.left
            }
            return current.value
        }

        /**
         * 查找树中的最大值
         * @returns {number} 树中的最大数值
         */
        findMax(){
            let current = this.root
            // 持续向右子树遍历直到叶子节点
            while(current.right){
                current = current.right
            }
            return current.value
        }
    }

    // 二叉搜索树功能测试
    const tree = new BinaryTree();

    tree.insert(10);
    tree.insert(5);
    tree.insert(15);
    tree.insert(3);
    tree.insert(7);

    console.log("In-order traversal:");
    tree.inOrder(); // 输出: 3, 5, 7, 10, 15

    console.log("Pre-order traversal:");
    tree.preOrder(); // 输出: 10, 5, 3, 7, 15

    console.log("Post-order traversal:");
    tree.postOrder(); // 输出: 3, 7, 5, 15, 10

    console.log("Level-order traversal:");
    tree.levelOrder(); // 输出: 10, 5, 15, 3, 7

    console.log("Minimum value:", tree.findMin()); // 输出: 3
    console.log("Maximum value:", tree.findMax()); // 输出: 15
    console.log("Search for 7:", tree.search(7)); // 输出: true
    console.log("Search for 12:", tree.search(12)); // 输出: false
</script>
</html>
